package SortAlgorithm;

public class 堆排序 implements ISort {

    /**
     * 利用堆来进行排序,牢记如何编写堆;
     * 不稳定;
     */

    @Override
    public int[] sort(int[] arr) {
        return this.heapSort(arr);
    }

    public int[] heapSort(int[] arr) {
        return arr;
    }

    // 最大堆
    static class MaxHeap {
        private int[] arr;

        public MaxHeap(int[] arr) {
            this.arr = arr;
            // 构造堆,从开头对每个节点进行上浮
            int index = 0;
            while (index < arr.length) {
                this.up(index);
                index++;
            }
            // 慢慢取出排序
            int maxLength = arr.length;
            index = this.arr.length - 1;
            while (index >= 0) {
                // 最大放到最后
                this.swap(arr, 0, index);
                // 下沉刚交换的
                this.down(0, maxLength - 1);
                index--;
                maxLength--;
            }
        }

        /**
         * 上浮和下沉都得实现
         */

        // 上浮构造
        private void up(int index) {
            if (index == 0) {
                // 是根节点了,就不用上浮了
                return;
            }
            // 因为是最大堆,大的在上面,大的才上浮
            int parentIndex = this.parentChildIndex(index);
            int parentNum = this.arr[parentIndex];
            int num = this.arr[index];
            if (parentNum < num) {
                this.swap(this.arr, index, parentIndex);
                // 递归
                this.up(parentIndex);
            }
        }

        /**
         * 为何多了一个maxLength? 因为为了在构造方法里直接进行排序,将根节点放到末尾后,将maxLength-1即可。
         *
         * @param index
         * @param maxLength
         */
        // 下沉维护
        private void down(int index, int maxLength) {
            if (index >= maxLength) {
                // 是最后的一个节点了,就不用下沉了
                return;
            }
            // 最大堆,小的在下面,比子节点小,那么就和子节点交换
            int leftIndex = this.leftChildIndex(index);
            if (leftIndex >= maxLength) {
                return;
            }
            int rightIndex = this.rightChildIndex(index);
            if (rightIndex >= maxLength) {
                // 数组长度有限,只有左节点的情况
                rightIndex = leftIndex;
            }
            int leftNum = this.arr[leftIndex];
            int rightNum = this.arr[rightIndex];
            int num = this.arr[index];
            // 下面两个节点大,那么就与最大的进行交换
            if (leftNum > num && rightNum > num) {
                // 谁大就和谁交换
                if (leftNum > rightNum) {
                    // 和左交换
                    this.swap(this.arr, leftIndex, index);
                    this.down(leftIndex, maxLength);
                } else {
                    // 和右交换
                    this.swap(this.arr, rightIndex, index);
                    this.down(rightIndex, maxLength);
                }
            } else if (leftNum > num) {
                this.swap(this.arr, leftIndex, index);
                this.down(leftIndex, maxLength);
            } else if (rightNum > num) {
                this.swap(this.arr, rightIndex, index);
                this.down(rightIndex, maxLength);
            }
            // 当前就是最大的了,stop
        }

        /**
         * 三个标
         */
        private int leftChildIndex(int index) {
            return index * 2 + 1;
        }

        private int rightChildIndex(int index) {
            return index * 2 + 2;
        }

        private int parentChildIndex(int index) {
            return (index - 1) / 2;
        }

        private void swap(int[] arr, int index1, int index2) {
            int num = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = num;
        }

    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 6, 8, 7, 3, 9};
        MaxHeap maxHeap = new MaxHeap(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

}
